/**
 * 面试题 04.05. 合法二叉搜索树
 * https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/
 */
public class Solutions_mianshi_04_05 {
    public static void main(String[] args) {
//        String treeStr = "[2 1 3]";  // output: true
        String treeStr = "[5 1 4 # # 3 6]";  // output: false

        TreeNode root = MyTreeNodeUtils.deserialize(treeStr);
        boolean result = isValidBST(root);
        System.out.println(result);
    }

    /**
     * 利用二叉搜索树的特征：任一节点的节点值都大于左子树上的节点值，小于右子树上的节点值
     * 中序遍历，记录下前一节点
     */
    static TreeNode prev;
    public static boolean isValidBST(TreeNode root) {
        // 每次执行 isValidBST 方法都还原类变量的值
        prev = null;
        return dfs(root);
    }

    static boolean dfs(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean leftRes = dfs(root.left);
        if (!leftRes) {
            // 已知结果为 false，提前结束
            return false;
        }
        if (prev != null && root.val <= prev.val) {
            // 检查当前递归节点值是否大于 prev 节点值
            return false;
        }
        prev = root;
        boolean rightRes = dfs(root.right);
        return rightRes;
    }
}
